package agent.strategy;

import agent.Agent;
import oracle.MoveTypes;
import oracle.Oracle;

/**
 * This is our abstract strategy class
 * It has such functions as the probability of reaching a square from a square
 * It also has our EM method
 * 
 * @author mdailey
 *
 */
public abstract class Strategy {
	/** The commit time */
	int commitTime = 10;
	/** The current row */
	int currRow;
	/** The current column */
	int currColumn;
	int numRoundsRemaining;
	int numRunsRemaining;	// how many runs through this same map we have left
	int numMovesRemaining;	/* of the 10 runs through each of the maps */
	int numMovesUsed;
	int penaltyDeath;	
	int maxRow;
	int maxCol;
	/** true if there is a terminal there, guess if there will be one */
	boolean terminals[][];
	/** the past terminals */
	boolean pastTerminals[][];
	/** true if there is a wall located there */
	boolean walls[][];
	/** A fairly accurate representation of the board */
	double theBoard[][];
	/** A more pessimistic board which favors getting to a terminal state */
	double pessimisticBoard[][] = null;
	/** A more optimistic board which favors perhaps exploration */
	double goodBoard[][] = null;
	/** true if tiles are visible now */
	boolean explored[][] = null;
	/** true if tiles are visible in the past */
	boolean exploredPast[][] = null;
	
	int manhattan =  0;
	BoardMemory myBoard;
	
	// this is just here for test purposes
	Agent myAgent = null;
	
	/** 
	 * Saves the board memory so we can update about our world
	 * @param myBoard
	 */
	public Strategy(BoardMemory myBoard){
		this.myBoard = myBoard;
	}
	
	/**
	 * Set the commit time for this strategy
	 * @param commitTime
	 */
	public void setCommitTime(int commitTime){
		this.commitTime = commitTime;
	}
	
	/**
	 * returns the next move object
	 * @param param1
	 * @param param2
	 * @param param3
	 * @return
	 */
	public nextDirObject nextMove(double param1, double param2, double param3){
		nextDirObject myO = new nextDirObject();
		myO.moveDirection = MoveTypes.KILL_SELF;
		return myO;
	}
	
	
	
	/** 
	 * Returns the number of terminals that are in the board
	 * @return
	 */
	public int getNumTerminals(){
		int sum=0;
		for(int r=0; r<maxRow;r++){
			for(int c=0; c<maxCol; c++){
				sum++;
			}
		}
		return sum;
	}
	
	/**
	 * This is where the agent needs to fill in these fields of this class
	 */
	public void setUpFields(){
		currRow = myAgent.currentPosition.row;
		currColumn = myAgent.currentPosition.column;
		numRoundsRemaining = Oracle.MAX_NUMBER_BOARDS - myAgent.oracle.getRoundNumber() - 1;
		numRunsRemaining = Oracle.MAX_NUMBER_RUNS - myAgent.oracle.getRunNumber() - 1;
		numMovesRemaining = myAgent.oracle.getNumMovesLeftInRound();
		numMovesUsed = myAgent.oracle.getCurrMoveNumber();
		penaltyDeath = Oracle.KILL_SELF_PENALTY;
		maxRow = Oracle.MAX_ROW;
		maxCol = Oracle.MAX_COL;
		terminals = new boolean[maxRow][maxCol];
		walls = new boolean[maxRow][maxCol];
		theBoard = new double[maxRow][maxCol];
		pessimisticBoard = new double[maxRow][maxCol];
		explored = new boolean[maxRow][maxCol];
		pastTerminals = new boolean[maxRow][maxCol];
		exploredPast = new boolean[maxRow][maxCol];
		goodBoard = new double[maxRow][maxCol];
		myBoard.fillInAccurateBoard(theBoard);
		myBoard.fillInPoorBoard(pessimisticBoard);
		myBoard.fillInOptimisticBoard(goodBoard);
		myBoard.fillInWallsAndTerminals(walls, terminals, pastTerminals, explored, exploredPast);
		
		//myAgent.fillInAccurateValues(theBoard);
		myAgent.fillInPoorValues(this.pessimisticBoard);
		myAgent.fillWallsAndTerminals(walls, terminals, pastTerminals, explored, exploredPast);
		myAgent.fillInAccurateValues(this.goodBoard);
		if(explored == null)
			System.err.println("its null");
		manhattan = Oracle.getMaxSightRange();
	}
	
	/**
	 * This will get a more accurate view of the world, a more up to date view
	 */
	public void setUpBMBoards(){
		setUpFields();
		/*myBoard.fillInWallsAndTerminals(walls, terminals, pastTerminals, explored, exploredPast);
		myBoard.fillInAccurateBoard(theBoard);
		myBoard.fillInPoorBoard(this.pessimisticBoard);*/
	}
	
	/**
	 * Set the agent for this strategy
	 * @param myAgentA
	 */
	public void setAgent(Agent myAgentA){
		myAgent = myAgentA;
		this.setUpFields();
	}
	
	/**
	 * This returns the maximum number of tiles that can ever be uncovered by a LOOK_AROUND move
	 * @return
	 */
	public int getMaxPossTilesEver(){
		int r = (int)(this.maxRow / 2.0);
		int c = (int)(this.maxCol/2.0);
		return this.numPossibleExpose(r,c);
	}
	
	/**
	 * returns the maximum possible amount of tiles that we can explore from (row,col)
	 * @param row
	 * @param col
	 * @return The number of possible tiles revealed
	 */
	public int numPossibleExpose(int row, int col){
		int num = 0;
		for(int r=0; r<maxRow; r++){
			for(int c=0; c< maxCol; c++){
				if((Math.abs(c-col)+Math.abs(r-row)) <= manhattan)
					num++;
			}
		}
		return num;
	}
	
	/**
	 * Returns true if a LOOK_AROUND move would expose the ending tile from the start tile
	 * @param startR
	 * @param startC
	 * @param endR
	 * @param endC
	 * @return
	 */
	public boolean isReachable(int startR,int startC,int endR,int endC){
		return (Math.abs(startR - endR) + Math.abs(startC-endC)) <= manhattan;
	}
	
	/**
	 * This is not accurate, but is used to trim our search space in other functions
	 * @param startR
	 * @param startC
	 * @param endR
	 * @param endC
	 * @param numMoves
	 * @return
	 */
	public boolean isReachableWithin(int startR, int startC, int endR, int endC, int numMoves){
		return (Math.abs(startR - endR) + Math.abs(startC-endC)) <= numMoves;
	}
	
	
	/**
	 * returns the number of tiles that are explored
	 * @return The number of tiles revealed
	 */
	public int totalNumExposed(){
		int num = 0;
		for(int r=0; r<maxRow; r++){
			for(int c=0; c< maxCol; c++){
				if(explored[r][c])
					num++;
			}
		}
		return num;
	}
	
	public boolean shouldExplore(int row, int col){
		return (1.0+this.numWillExposeAtDistance(row, col, this.manhattan)) *.7 > 
		  (1.0 + this.numWillExposeAtDistance(row, col, this.manhattan - 2)) && this.numWillExpose(row, col) > this.manhattan*2;
	}
	
	/**
	 * returns the number of tiles that we will expose from (row,col)
	 * @param row
	 * @param col
	 * @return The number of tiles actually revealed
	 */
	public int numWillExpose(int row, int col){
		int num = 0;
		for(int r=0; r<maxRow; r++){
			for(int c=0; c< maxCol; c++){
				if(!explored[r][c] && (Math.abs(c-col)+Math.abs(r-row)) <= manhattan)
					num++;
			}
		}
		return num;
	}
	
	/**
	 * Returns how many we will expose from this distance
	 * @param row
	 * @param col
	 * @param distance
	 * @return
	 */
	public int numWillExposeAtDistance(int row, int col, int distance){
		int num = 0;
		for(int r=0; r<maxRow; r++){
			for(int c=0; c< maxCol; c++){
				if(!explored[r][c] && (Math.abs(c-col)+Math.abs(r-row)) <= distance)
					num++;
			}
		}
		return num;
	}
	
	public int calculateDistance(int x1, int y1, int x2, int y2){
		return Math.abs(x1-x2) + Math.abs(y1-y2);
	}
	
	/**
	 * returns the manhattan distance affected by the explore action
	 * @param maxRow
	 * @param maxCol
	 * @return
	 */
	public int getMan(int maxRow, int maxCol){
		return (int) Math.ceil((maxRow * maxCol)/100.0);
	}
	
	
	
	/**
	 * This calculates the probability of reaching a square in at most numMoves if the first move
	 * is done as specified in the nextDirObject
	 * @param startRow	The starting row of the agent
	 * @param startCol The starting column of the agent
	 * @param endR The ending row of the agent
	 * @param endC The ending column of the agent
	 * @param numMoves The max number of moves to reach the square
	 * @param maxRow The max number of rows in the board
	 * @param maxCol The max number of columns in the board
	 * @return The [0,1] probability of getting to the destination
	 */
	public nextDirObject probReachSquareFromTo(int startRow, int startCol, int endR, int endC, int numMoves,
			int maxRow, int maxCol){
		boolean[][] tempTerminals = new boolean[maxRow][maxCol];
		tempTerminals[endR][endC] = true;
		double temptempTheBoard[][] = new double[maxRow][maxCol];
		temptempTheBoard[endR][endC] = 1;
		nextDirObject myR = this.probReachSquare(startRow, startCol, endR, endC, numMoves);
		if(myR == null){
			System.out.println("myR is null");
		}
		// myR now says that moving in a certain direction maximizes prob at this amount
		return myR;
	}/**
	 * This calculates the probability of reaching a square in at most numMoves if the first move
	 * is done as specified in the nextDirObject
	 * @param startRow	The starting row of the agent
	 * @param startCol The starting column of the agent
	 * @param endR The ending row of the agent
	 * @param endC The ending column of the agent
	 * @param numMoves The max number of moves to reach the square
	 * @param maxRow The max number of rows in the board
	 * @param maxCol The max number of columns in the board
	 * @return The [0,1] probability of getting to the destination
	 */
	public nextDirObject probReachSquareFromTo(int startRow, int startCol, int endR, int endC, int numMoves){
		this.maxRow = Oracle.MAX_ROW;
		this.maxCol = Oracle.MAX_COL;
		boolean[][] tempTerminals = new boolean[maxRow][maxCol];
		tempTerminals[endR][endC] = true;
		double temptempTheBoard[][] = new double[maxRow][maxCol];
		temptempTheBoard[endR][endC] = 1;
		nextDirObject myR = this.probReachSquare(startRow, startCol, endR, endC, numMoves);
		if(myR == null){
			System.out.println("myR is null");
		}
		// myR now says that moving in a certain direction maximizes prob at this amount
		return myR;
	}
	
	/**
	 * This calculates the optimal path to maximize our expected utility with the board input
	 * the values of squares are given heuristic values based on a function that looks at 
	 * how many squares that are explored from there and prob of reaching there and other factors
	 * 
	 * @param theBoard This holds some heuristic value of the world
	 * @param terminals	where true, the base case doesnt add the death penalty
	 * @param walls	where true, there is a wall
	 * @param beliefs
	 * @param explored
	 * @param startRow
	 * @param startCol
	 * @param numMovesLeft		How many moves we have to reach this place
	 * @param penaltyDeath		If dont terminal[r][c]=true, then we get assessed this penalty (could be positive)
	 * @param maxRows
	 * @param maxColumns
	 * @param numTurnsRemaining		not currently used
	 * @param valueOfInformation	not currently used
	 */
	public nextDirObject getNextDirection(double[][] theBoard, boolean[][] terminals, boolean[][] walls, 
		double[][]beliefs, boolean[][] explored, int startRow, int startCol,
		int numMovesLeft, int penaltyDeath, int maxRows, int maxColumns,
		int numTurnsRemaining, double valueOfInformation){
		
		if(numMovesLeft == 0){
			return null;
		}
		
		/* this is our dynamic programming solution to path planning
		 * dynBoard[r][c][0] represents the utility of a square with 0 moves remaining
		 * These are calculated as either the death penalty or the terminal value
		 * We also have that dynBoard[r][c][1], you can either kill yourself
		 * or move to an adjacent square\explore*/
		//double dynBoard[][][] = new double[maxRows][maxColumns][numMovesLeft+1];
		// We do it Smarter!!!
		double currDynBoard[][][] = new double[maxRows][maxColumns][2];
		
		double rightA, leftA, downA, upA;
		double[] moveVals = new double[5];
		double probC = .0666666666;
		double attemptR ,attemptL,attemptU ,attemptD; 
		
		// our base 
		for(int r=0; r<maxRows; r++){
			for(int c=0; c<maxColumns;c++){
				if(terminals[r][c]){
				//	dynBoard[r][c][0] = theBoard[r][c];
					currDynBoard[r][c][0] = theBoard[r][c];
					currDynBoard[r][c][1] = theBoard[r][c];
				}else{
				//	dynBoard[r][c][0] = theBoard[r][c] + penaltyDeath;
					currDynBoard[r][c][0] = theBoard[r][c] + penaltyDeath;
					currDynBoard[r][c][1] = theBoard[r][c] + penaltyDeath;
				}
			//	System.out.println("("+r+","+c+") "+ currDynBoard[r][c][1]);
			}
		}
		
		// our remaining cases
		for(int round = 1; round <= numMovesLeft; round++){
			/* copy our old timestep in */
			for(int r=0; r<maxRows; r++){
				for(int c=0; c<maxColumns;c++){
					currDynBoard[r][c][0] = currDynBoard[r][c][1];
				}
			}
			
			for(int r=0; r<maxRows; r++){
				for(int c=0; c<maxColumns;c++){
					// calculate right
					if(c+1 >= maxColumns || walls[r][c+1]){
					//	rightA = dynBoard[r][c][round - 1] + theBoard[r][c];
						rightA = currDynBoard[r][c][0] + theBoard[r][c];
						if(terminals[r][c])
							rightA = theBoard[r][c];
					}else{
					//	rightA = dynBoard[r][c+1][round - 1] + theBoard[r][c+1];
						rightA = currDynBoard[r][c+1][0] + theBoard[r][c+1];
						if(terminals[r][c+1])
							rightA = Math.max(rightA, theBoard[r][c+1]);
					}
					// calculate left
					if(c-1 < 0 || walls[r][c-1]){
					//	leftA = dynBoard[r][c][round - 1] + theBoard[r][c];
						leftA = currDynBoard[r][c][0] + theBoard[r][c];
						if(terminals[r][c])
							leftA = theBoard[r][c];
					}else{
					//	leftA = dynBoard[r][c-1][round - 1] + theBoard[r][c-1];
						leftA = currDynBoard[r][c-1][0] + theBoard[r][c-1];
						if(terminals[r][c-1])
							leftA =  theBoard[r][c-1];
					}
					// calculate down
					if(r+1 >= maxRows || walls[r+1][c]){
					//	downA = dynBoard[r][c][round - 1]+ theBoard[r][c];
						downA = currDynBoard[r][c][0] + theBoard[r][c];
						if(terminals[r][c])
							downA = theBoard[r][c];
					}else{
					//	downA = dynBoard[r+1][c][round - 1] + theBoard[r+1][c];
						downA = currDynBoard[r+1][c][0] + theBoard[r+1][c];
						if(terminals[r+1][c])
							downA = theBoard[r+1][c];
					}
					// calculate up
					if(r-1 < 0 || walls[r-1][c]){
					//	upA = dynBoard[r][c][round - 1] + theBoard[r][c];
						upA = currDynBoard[r][c][0] + theBoard[r][c];
						if(terminals[r][c])
							upA =theBoard[r][c];
					}else{
					//	upA = dynBoard[r-1][c][round - 1] + theBoard[r-1][c];
						upA = currDynBoard[r-1][c][0] + theBoard[r-1][c];
						if(terminals[r-1][c])
							upA = theBoard[r-1][c];
					}
				
					// now take max (using probabilities) include possibility of killing self
					attemptR = .80*rightA + probC*leftA + probC*upA + probC*downA;
					attemptL = .80*leftA + probC*rightA + probC*upA + probC*downA;
					attemptU = .80*upA + probC*leftA + probC*rightA + probC*downA;
					attemptD = .80*downA + probC*leftA + probC*upA + probC*rightA;
					moveVals[0] = penaltyDeath;
					moveVals[MoveTypes.RIGHT] = attemptR;
					moveVals[MoveTypes.LEFT] = attemptL;
					moveVals[MoveTypes.UP] = attemptU;
					moveVals[MoveTypes.DOWN] = attemptD;
					int maxPos = 0;
					for(int i = 1; i<5; i++){
						if(moveVals[i] > moveVals[maxPos])
							maxPos = i;
					}
				/*	if(moveVals[maxPos] > 100){
						System.out.println(round + " ("+r+","+c+") "+ moveVals[maxPos] + " " + theBoard[r][c]);
						//return null;
					}*/
					
					// position i now holds the maximum position of the optimal move 
					currDynBoard[r][c][1] = moveVals[maxPos];
					/* If we are on a terminal we must end */
					if(terminals[r][c]){
					//	dynBoard[r][c][round] = Math.max(dynBoard[r][c][round], theBoard[r][c]);
						currDynBoard[r][c][1] = Math.max(currDynBoard[r][c][1], theBoard[r][c]);
					}
				}
			}
		}
		
		/* now we are asked for a specific position what is the optimal move*/
		if(startCol+1 >= maxColumns || walls[startRow][startCol+1]){
		//	rightA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
			rightA = currDynBoard[startRow][startCol][0] + theBoard[startRow][startCol];
		}else{
		//	rightA = dynBoard[startRow][startCol+1][numMovesLeft - 1] + theBoard[startRow][startCol+1];
			rightA = currDynBoard[startRow][startCol+1][0] + theBoard[startRow][startCol];
		}
		// calculate left
		if(startCol-1 < 0 || walls[startRow][startCol-1]){
		//	leftA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
			leftA = currDynBoard[startRow][startCol][0] + theBoard[startRow][startCol];
		}else{
		//	leftA = dynBoard[startRow][startCol-1][numMovesLeft - 1] + theBoard[startRow][startCol-1];
			leftA = currDynBoard[startRow][startCol-1][0] + theBoard[startRow][startCol];
		}
		// startColalstartColulate down
		if(startRow+1 >= maxRows || walls[startRow+1][startCol]){
		//	downA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
			downA = currDynBoard[startRow][startCol][0] + theBoard[startRow][startCol];
		}else{
		//	downA = dynBoard[startRow+1][startCol][numMovesLeft - 1] + theBoard[startRow+1][startCol];
			downA = currDynBoard[startRow+1][startCol][0] + theBoard[startRow][startCol];
		}
		// startColalstartColulate up
		if(startRow-1 < 0 || walls[startRow-1][startCol]){
		//	upA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
			upA = currDynBoard[startRow][startCol][0] + theBoard[startRow][startCol];
		}else{
		//	upA = dynBoard[startRow-1][startCol][numMovesLeft - 1] + theBoard[startRow-1][startCol];
			upA = currDynBoard[startRow-1][startCol][0] + theBoard[startRow][startCol];
		}
		// each move is probabilistic except kill self
		attemptR = .80*rightA + probC*leftA + probC*upA + probC*downA;
		attemptL = .80*leftA + probC*rightA + probC*upA + probC*downA;
		attemptU = .80*upA + probC*leftA + probC*rightA + probC*downA;
		attemptD = .80*downA + probC*leftA + probC*upA + probC*rightA;
	//	System.out.println(attemptR + " " + attemptL + " " + attemptU + " " + attemptD);
		
		moveVals[0] = penaltyDeath;
		moveVals[MoveTypes.RIGHT] = attemptR;
		moveVals[MoveTypes.LEFT] = attemptL;
		moveVals[MoveTypes.UP] = attemptU;
		moveVals[MoveTypes.DOWN] = attemptD;
		int maxPos = 0;
		for(int i = 1; i<5; i++){
			if(moveVals[i] >= moveVals[maxPos])
				maxPos = i;
		}
		nextDirObject toReturn = new nextDirObject();
		toReturn.moveDirection = maxPos;
		if(maxPos == 0){
			toReturn.moveDirection = MoveTypes.KILL_SELF;
			toReturn.adviseMove = false;
		}
		toReturn.expectedUtility =  moveVals[maxPos];
		return toReturn;
	}
	
	
	/**
	 * This is used to calculate probability of getting to a square
	 * The square that we are trying to get to is initialized with 1
	 * The value of all other squares are assigned a value of 0
	 * @param temptempTheBoard	double filled with values, all = 0 except square trying to get to
	 * @param startRow	The starting row
	 * @param startCol The starting column
	 * @param numMovesLeft The maximum number of moves that we have to reach there
	 * @param penDeath	This should be set to 0
	 * @return
	 */
	public nextDirObject probReachSquare(int startRow, int startCol, int endRow, int endCol, int numMovesLeft){
			boolean modTerms[][] = new boolean[this.maxRow][this.maxCol];
			modTerms[endRow][endCol] = true;
			double modVals[][] = new double[this.maxRow][this.maxCol];
			modVals[endRow][endCol] = 1;
			nextDirObject toReturn = this.getNextDirection(modVals, modTerms, walls, null, null, startRow, startCol, numMovesLeft, 0, maxRow, maxCol, numMovesLeft, 0);
			if (toReturn == null)
			{
				toReturn = new nextDirObject();
				toReturn.probSuccess = 0;
				toReturn.expectedUtility = 0;
			}
			toReturn.probSuccess = toReturn.expectedUtility;
			return toReturn;
	}
	
	/**
	 * This calculates the optimal path to maximize our expected utility with the board input
	 * the values of squares are given heuristic values based on a function that looks at 
	 * how many squares that are explored from there and prob of reaching there and other factors
	 * 
	 * @param theBoard This holds some heuristic value of the world
	 * @param terminals	where true, the base case doesnt add the death penalty
	 * @param walls	where true, there is a wall
	 * @param beliefs
	 * @param explored
	 * @param startRow
	 * @param startCol
	 * @param numMovesLeft		How many moves we have to reach this place
	 * @param penaltyDeath		If dont terminal[r][c]=true, then we get assessed this penalty (could be positive)
	 * @param maxRows
	 * @param maxColumns
	 * @param numTurnsRemaining		not currently used
	 * @param valueOfInformation	not currently used
	 */
	public nextDirObject getNextDirection2(double[][] theBoard, boolean[][] terminals, boolean[][] walls, 
		double[][]beliefs, boolean[][] explored, int startRow, int startCol,
		int numMovesLeft, int penaltyDeath, int maxRows, int maxColumns,
		int numTurnsRemaining, double valueOfInformation){
		
		if(numMovesLeft == 0){
			return null;
		}
		
		/* this is our dynamic programming solution to path planning
		 * dynBoard[r][c][0] represents the utility of a square with 0 moves remaining
		 * These are calculated as either the death penalty or the terminal value
		 * We also have that dynBoard[r][c][1], you can either kill yourself
		 * or move to an adjacent square\explore*/
		double dynBoard[][][] = new double[maxRows][maxColumns][numMovesLeft+1];
		double rightA, leftA, downA, upA;
		double[] moveVals = new double[5];
		double probC = .0666666666;
		double attemptR ,attemptL,attemptU ,attemptD; 
		
		// our base 
		for(int r=0; r<maxRows; r++){
			for(int c=0; c<maxColumns;c++){
				if(terminals[r][c]){
					dynBoard[r][c][0] = theBoard[r][c];
				}else{
					dynBoard[r][c][0] = theBoard[r][c] + penaltyDeath;
				}
			//	System.out.println(r+","+c +  "  with val " + dynBoard[r][c][0]);
			}
		}
		
		// our remaining cases
		for(int round = 1; round <= numMovesLeft; round++){
			for(int r=0; r<maxRows; r++){
				for(int c=0; c<maxColumns;c++){
					// calculate right
					if(c+1 >= maxColumns || walls[r][c+1]){
						rightA = dynBoard[r][c][round - 1] + theBoard[r][c];
						if(terminals[r][c])
							rightA = Math.max(rightA, theBoard[r][c]);
					}else{
						rightA = dynBoard[r][c+1][round - 1] + theBoard[r][c+1];
						if(terminals[r][c+1])
							rightA = Math.max(rightA, theBoard[r][c+1]);
					}
					// calculate left
					if(c-1 < 0 || walls[r][c-1]){
						leftA = dynBoard[r][c][round - 1] + theBoard[r][c];
						if(terminals[r][c])
							leftA = Math.max(leftA, theBoard[r][c]);
					}else{
						leftA = dynBoard[r][c-1][round - 1] + theBoard[r][c-1];
						if(terminals[r][c-1])
							leftA = Math.max(leftA, theBoard[r][c-1]);
					}
					// calculate down
					if(r+1 >= maxRows || walls[r+1][c]){
						downA = dynBoard[r][c][round - 1]+ theBoard[r][c];
						if(terminals[r][c])
							downA = Math.max(downA, theBoard[r][c]);
					}else{
						downA = dynBoard[r+1][c][round - 1] + theBoard[r+1][c];
						if(terminals[r+1][c])
							downA = Math.max(downA, theBoard[r+1][c]);
					}
					// calculate up
					if(r-1 < 0 || walls[r-1][c]){
						upA = dynBoard[r][c][round - 1] + theBoard[r][c];
						if(terminals[r][c])
							upA = Math.max(upA, theBoard[r][c]);
					}else{
						upA = dynBoard[r-1][c][round - 1] + theBoard[r-1][c];
						if(terminals[r-1][c])
							upA = Math.max(upA, theBoard[r-1][c]);
					}
				
					// now take max (using probabilities) include possibility of killing self
					attemptR = .80*rightA + probC*leftA + probC*upA + probC*downA;
					attemptL = .80*leftA + probC*rightA + probC*upA + probC*downA;
					attemptU = .80*upA + probC*leftA + probC*rightA + probC*downA;
					attemptD = .80*downA + probC*leftA + probC*upA + probC*rightA;
					moveVals[0] = penaltyDeath;
					moveVals[MoveTypes.RIGHT] = attemptR;
					moveVals[MoveTypes.LEFT] = attemptL;
					moveVals[MoveTypes.UP] = attemptU;
					moveVals[MoveTypes.DOWN] = attemptD;
					int maxPos = 0;
					for(int i = 1; i<5; i++){
						if(moveVals[i] > moveVals[maxPos])
							maxPos = i;
					}
					// position i now holds the maximum position of the optimal move 
					dynBoard[r][c][round] = moveVals[maxPos];
					/* maybe leave this in about if we are on a terminal we may end */
					if(terminals[r][c]){
						dynBoard[r][c][round] = Math.max(dynBoard[r][c][round], theBoard[r][c]);
					}
				}
			}
		}
		
		/* now we are asked for a specific position what is the optimal move*/
		if(startCol+1 >= maxColumns || walls[startRow][startCol+1]){
			rightA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
		}else{
			rightA = dynBoard[startRow][startCol+1][numMovesLeft - 1] + theBoard[startRow][startCol+1];
		}
		// calculate left
		if(startCol-1 < 0 || walls[startRow][startCol-1]){
			leftA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
		}else{
			leftA = dynBoard[startRow][startCol-1][numMovesLeft - 1] + theBoard[startRow][startCol-1];
		}
		// startColalstartColulate down
		if(startRow+1 >= maxRows || walls[startRow+1][startCol]){
			downA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
		}else{
			downA = dynBoard[startRow+1][startCol][numMovesLeft - 1] + theBoard[startRow+1][startCol];
		}
		// startColalstartColulate up
		if(startRow-1 < 0 || walls[startRow-1][startCol]){
			upA = dynBoard[startRow][startCol][numMovesLeft - 1] + theBoard[startRow][startCol];
		}else{
			upA = dynBoard[startRow-1][startCol][numMovesLeft - 1] + theBoard[startRow-1][startCol];
		}
		// each move is probabilistic except kill self
		attemptR = .80*rightA + probC*leftA + probC*upA + probC*downA;
		attemptL = .80*leftA + probC*rightA + probC*upA + probC*downA;
		attemptU = .80*upA + probC*leftA + probC*rightA + probC*downA;
		attemptD = .80*downA + probC*leftA + probC*upA + probC*rightA;
		
		moveVals[0] = penaltyDeath;
		moveVals[MoveTypes.RIGHT] = attemptR;
		moveVals[MoveTypes.LEFT] = attemptL;
		moveVals[MoveTypes.UP] = attemptU;
		moveVals[MoveTypes.DOWN] = attemptD;
		int maxPos = 0;
		for(int i = 1; i<5; i++){
			if(moveVals[i] > moveVals[maxPos])
				maxPos = i;
		}
		nextDirObject toReturn = new nextDirObject();
		toReturn.moveDirection = maxPos;
		if(maxPos == 0){
			toReturn.moveDirection = MoveTypes.KILL_SELF;
			toReturn.adviseMove = false;
		}
		toReturn.expectedUtility =  moveVals[maxPos];
		return toReturn;
	}
}

